package com.cskaoyan.javase.recursion._3hanoi;

/**
 * 汉诺塔问题:
 * 相传在古印度的圣庙中，有一种被称之为汉诺塔（也叫河内塔，Hanoi）的游戏
 * 简单来说：有三个塔1，2，3，塔1上有 N 个（N>1）穿孔圆盘，大盘在下，小盘在上
 * 要求按下列规则将所有圆盘移至塔3：
 * 	1，每次只能移动一个圆盘
 * 	2，大盘一定在小盘之下
 * 提示：可将圆盘临时置于塔2，也可以将塔1的圆盘重新移回塔1，但都必须遵循上述两条规则
 * 问：当塔1上有N（N>=1）个圆盘时，最少要移动多少次？（注意是最少）
 *
 * 这个汉诺塔问题,如何使用递归求解呢?
 * 如何分解N个盘子的汉诺塔问题,找到递归体呢?
 *
 * 分解:
 *      有一步是必须要做的:
 *      把塔1上最大的盘子从塔1移到塔3上去,这要求塔3是空的
 *      进而要求塔1上除了最大盘子外的所有盘子,都必须在塔2上
 *
 *      完成把塔1上最大的盘子从塔1移到塔3上去后
 *      这时就需要把塔2上除了最大盘子外的所有盘子全部移到塔3上去
 *
 *      以上就能够完成汉诺塔问题,这样就是一个分解的思路.
 *
 * 假设N个盘子的汉诺塔问题,至少需要f(N)步解决它
 * 那么f(N)就分解为:
 *      1.塔1上除了最大盘子外的所有盘子,都必须在塔2上,需要f(N-1)步
 *      2.把塔1上最大的盘子从塔1移到塔3上去,需要1步
 *      3.把塔2上除了最大盘子外的所有盘子全部移到塔3上去,需要f(N-1)步
 * 所以分解后:
 *      f(N) = f(N-1) + 1 + f(N-1) (这就是递归体)
 * 当然分解不可能无限进行:
 *      当N = 1时,f(N) = 1 (这就是递归的出口)
 *
 * 已知 f(N) = f(N-1) + 1 + f(N-1)
 * 求f(N)的通项公式
 *
 * f(N) = 2(f(N-1)) + 1
 * f(N) + 1 = 2(f(N-1) + 1)
 * (f(N) + 1) / ((f(N-1) + 1) ) = 2
 * 所以:
 * f(N) + 1 = 2^n
 * f(N) = 2^n - 1
 *
 * @since 11:33
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(hanoi(30));
    }

    // 递归求解汉诺塔问题
    public static long hanoi(int n) {
        // 递归的出口
        if (n == 1) {
            return 1;
        }
        // 递归体
        return hanoi(n - 1) + 1 + hanoi(n - 1);
    }
}
